package com.lihui.exercises;

/**
 * 功能描述
 *
 * @author wileda
 * @date 2022/10/12  9:52
 */
public class Exe_LinkedList01 {
    private static class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }
    //删除所有key值
    public ListNode removeElements(ListNode head,int val){
        if(head == null){
            return null;
        }
        ListNode prev = head;
        ListNode current = head.next;
        while (current != null){
            if (current.val == val){
                prev.next = current.next;
            }else {
                prev = current;
            }
            current = current.next;
        }
        if (head.val == val){
            head = head.next;
        }
        return head;
    }
    //反转链表
    public ListNode reverseList(ListNode head) {
        if(head == null){
            return null;
        }
        ListNode prev = null;
        ListNode current = head;
        while (current != null){
            ListNode nextNode = current.next;
            current.next = prev;
            prev = current;
            current = nextNode;
        }
        return prev;
    }

    //找出链表中间节点
    public ListNode middleNode(ListNode head) {
        if (head == null){
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
    // 链表倒数第k个节点
    public static ListNode findKthToTail(ListNode head, int k) {
        if (head == null || k <= 0){
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        for (int i = 1; i < k; i++) {
            if (fast.next == null){
                return null;
            }
            fast = fast.next;
        }
        while (fast.next != null){
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
    //合并两个有序链表
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list2 == null){
            return list1;
        }
        if (list1 == null){
            return list2;
        }

        ListNode tempHead = new ListNode(-1);
        ListNode current = tempHead;
        while (list1 != null && list2 != null){
            if (list1.val < list2.val){
                current.next = list1;
                current = current.next;
                list1 = list1.next;
            }else {
                current.next = list2;
                current = current.next;
                list2 = list2.next;
            }
        }
        if (list1 != null){
            current.next = list1;
        }
        if (list2 != null){
            current.next = list2;
        }
        return tempHead.next;
    }
    // 链表分割
    public ListNode partition(ListNode head, int x) {
        if (head == null){
            return null;
        }
        ListNode firstHead = null;
        ListNode firstTail = null;
        ListNode secondHead = null;
        ListNode secondTail = null;
        ListNode current = head;
        while (current != null){
            if (current.val < x){
                if (firstHead == null){
                    firstHead = current;
                    firstTail = current;
                }else {
                    firstTail.next = current;
                    firstTail = firstTail.next;
                }
            }else {
                if (secondHead == null){
                    secondHead = current;
                    secondTail = current;
                }else {
                    secondTail.next = current;
                    secondTail = secondTail.next;
                }
            }
            current = current.next;
            if (firstHead == null){
                secondTail.next = null;
                return secondHead;
            }
            if(secondHead == null){
                firstTail.next = null;
                return firstHead;
            }
        }
        firstTail.next = secondHead;
        secondTail.next = null;
        return firstHead;
    }
}
